package com.xxwy.sort.nlogn;

import com.sun.org.apache.bcel.internal.generic.SWAP;
import com.xxwy.sort.Sort;
import com.xxwy.sort.SortHelper;

/**
 * @author xxwy
 */
public class QuickSort implements Sort {


    @Override
    public void sort(int[] array, int n) {
        quicksort(array, 0, n - 1);
    }

    private void quicksort(int[] array, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition(array, l, r);
        quicksort(array, l, p - 1);
        quicksort(array, l, p + 1);
    }

    /**
     * 对arr[l..r]部分进行partition操作
     *
     * @param array
     * @param l
     * @param r
     * @return
     */
    private int partition(int[] array, int l, int r) {
        int e = array[l];
        //arr[l+1...j] < e l+1---l初始的时候不存在
        //arr[j+1....i)>e  l+1---l初始的时候不存在
        //j的作用就是记住中位数
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (array[i] < e) {
                //当前考察的元素和比它的第一个换
                SortHelper.swap(array,j+1,i);
                j++;
            }
        }
        SortHelper.swap(array,l,j);
        return j;
    }

}
